package com.example.rwq_test.niuke.stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 获取数组中第K小
 *
 * @author renweiqiang
 * @version 1.0.0
 * @createTime 2023/12/12
 */
public class MinKth {


    private static final Stack<Integer> nums = new Stack<>();
    private static final Stack<Character> ops = new Stack<>();
    public static void main(String[] args) {
        String str =  "1 + (-1-2*3)";
        System.out.println(cal(str));
    }

    private static Integer cal(String str) {
        if (str == null || str == "") {
            return 0;
        }
        str = str.replace(" ", "");
        doCal(str, 0);
        return nums.pop();
    }

    private static void doCal(String str, int i) {
        for (; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                i = doHandleBracket(str, i);
            } else if (Character.isDigit(str.charAt(i))) {
                i = doHandleNum(str, i);
            } else {
                if (str.charAt(i) == '-' && i != 0 && !Character.isDigit(str.charAt(i-1))) {
                    i = doHandleNum(str, i);
                } else {
                    ops.push(str.charAt(i));
                }
            }
        }
        Deque<Integer> ints = new ArrayDeque<>();
        Deque<Character> opArr = new ArrayDeque<>();
        while (!ops.isEmpty()) {
            if (ops.peek() == '*' || ops.peek() == '/') {
                doHandleMulOrDiv();
            } else {
                ints.offer(nums.pop());
                opArr.offer(ops.pop());
            }
        }
        int result = nums.isEmpty() ? 0 : nums.pop();
        while (!opArr.isEmpty()) {
            Integer num = 0;
            if (!ints.isEmpty()) {
                num = ints.pollLast();
            }
            result = (opArr.pollLast() == '+') ? (result + num) : (result - num);
        }
        nums.push(result);
    }

    private static Integer doHandleBracket(String str, int i) {
        if (str.charAt(i) != '(') {
            return i;
        }
        ops.push(str.charAt(i++));
        for (; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                i = doHandleBracket(str, i);
            } else if (str.charAt(i) == ')') {
                doHandleBracket();
                return i;
            } else if (Character.isDigit(str.charAt(i))) {
                i = doHandleNum(str, i);
            } else {
                ops.push(str.charAt(i));
            }
        }
        return --i;
    }

    private static void doHandleBracket() {
        Deque<Integer> ints = new ArrayDeque<>();
        Deque<Character> opArr = new ArrayDeque<>();
        while (ops.peek() != '(') {
            if (ops.peek() == '*' || ops.peek() == '/') {
                doHandleMulOrDiv();
            } else {
                doHandlePlusOrSub(ints, opArr);
            }
        }
        ops.pop();
        int result = nums.pop();
        while (!opArr.isEmpty()) {
            result = (opArr.pollLast() == '+') ? (result + ints.pollLast()) : (result - ints.pollLast());
        }
        nums.push(result);
    }

    private static void doHandlePlusOrSub(Deque<Integer> ints, Deque<Character> opArr) {
        while (ops.peek() == '+' || ops.peek() == '-') {
            ints.offer(nums.pop());
            opArr.offer(ops.pop());
        }
    }

    private static void doHandleMulOrDiv() {
        Deque<Integer> ints = new ArrayDeque<>();
        Deque<Character> opArr = new ArrayDeque<>();
        ints.offer(nums.pop());
        while (!ops.isEmpty() && (ops.peek() == '*' || ops.peek() == '/')) {
            opArr.offer(ops.pop());
            ints.offer(nums.pop());
        }
        int result = ints.pollLast();
        while (!opArr.isEmpty()) {
            result = (opArr.pollLast() == '*') ? (result * ints.pollLast()) : (result / ints.pollLast());
        }
        nums.push(result);
    }

    private static Integer doHandleNum(String str, int i) {
        if (!Character.isDigit(str.charAt(i))) {
            nums.push(0 - Character.getNumericValue(str.charAt(++i)));
            i++;
        } else {
            nums.push(Character.getNumericValue(str.charAt(i++)));
        }
        while (i < str.length() && Character.isDigit(str.charAt(i))) {
            nums.push(nums.pop() * 10 + Character.getNumericValue(str.charAt(i++)));
        }
        return --i;
    }


//    public static void main(String[] args) {
//        int[] nums = {9, 8, 7, 4 ,5, 6, 9, 8, 7};
//        int k = 8;
//        System.out.println(getMinKth(nums, k));
//    }

    public static int getMinKth(int[] arr, int k) {
        return getMinKth(arr, 0, arr.length - 1, k);
    }

    public static int getMinKth(int[] arr, int start, int end, int k) {
        int base = arr[start];
        int left = start;
        int right = end;

        while (left < right) {
            while (arr[right] >= base && left < right) {
                right --;
            }
            while (arr[left] <= base && left < right) {
                left ++;
            }

            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }

        if (left == k -1) {
            return base;
        }
        arr[start] = arr[left];
        arr[left] = base;

        if (left > k - 1) {
            return getMinKth(arr, start, left - 1, k);
        } else {
            return getMinKth(arr, left + 1, end, k);
        }
    }
}
